The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure. Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in the present disclosure and are not admitted to be prior art by inclusion in this section.
Many cryptographic operations, such as the Rivest, Shamir and Adleman (“RSA”) cryptographic process, may rely on one or more modular exponentiations. A modular exponentiation may include operations to determine a value for ax mod m for input values a, x, and m. In various techniques, a “windowed” exponentiation process may be performed based on a “window size” value w. In such a w-ary modular exponentiation, a loop may iterate through exponent bits in groups of w bits during calculation of an exponentiation result.
For example, the following w-ary modular exponentiation process uses known calculations called Montgomery Multiplications (or “MMs”) to determine a modular exponentiation result. The process may take as input values m, a (which may be less than m), and a secret exponent value x to compute ax mod m as an output. x may be expressed based on a window size parameter w asx=x0+x12w+x222w+ . . . +xk2kw where 0≦x0,x1, . . . , xk≦2w−1. The process may also rely on a Montgomery parameter s, as well as a pre-computed value c2=22s mod m.
The process may be expressed as follows. In the expression of the process,
Montgomery Multiplications are referred to as “MMs.”
1.    a′ = MM(a,c2)2.    m[0] = MM(c2,1)3.    m[1] = a′4.   For i = 2,...,2w − 1     4.1   m[i] = MM(m[i−1],a′)End For5.   Store m[0],...,m[2w − 1] in a table A6.   Retrieve m[xk] from table A7.    h = m[xk]8.   For i = k − 1,...,0     8.1   For j = 1,...,w      8.1.1  h = MM(h,h)     End For     8.2   Retrieve m[xi] from table A     8.3   h = MM(h,m[xi])End For9.   h = MM(h,1)Return h
MM results may have a bit-size equal to the number of bits in the modulus (m) value. As detailed above, a table of these MM results may be generated during execution of a windowed modular exponentiation process. As shown above, the table may hold 2w MM result entries. These stored MM results may later be retrieved and used to calculate the modular exponentiation output through further MM calculations.
However, this process may present security vulnerabilities. If cached memory is used to store the MM results, the MM results may be vulnerable to a side-channel attack. In some side-channel attacks, a spy process running in one thread can store values into memory at the locations that the exponentiation process (in another thread) will use for its MM table. The spy process may then wait for an iteration of the RSA process to occur and then reads the spy process's values back.
While the spy process may not be able to see the values written by the RSA process, the spy process may measure the response time for its own reads. If a spy read takes longer than expected, that may then mean that the associated portion of the cache was written to by the RSA process, evicting the spy's value in the cache. The spy process may then be able to recover w bits of the secret exponent x. Over time, the entire secret x value may be compromised.